/*!
 * \file StabBranching.cpp
 *
 * \date May 18, 2014
 * \author correa
 */
#include <StabBranching.h>

using namespace std;

StabBranching::StabBranching(Grafo& g, ReservaClique * reserva) : FactoryDesigualdad(), _desigualdades(), _vertices(&g.vertices()),
		_grados(g.grados<double>()),
		_param(RD, Goloso, RD, Clique, g.getN(), 3, 25, 0.15, 40), _clique(g.getN()),
		_nocliqueados(g.getN()), _reserva(reserva), _ninitialm(0), _grafo(g)
{
	_eleccionClqFactory = new GeneradorClique(_vertices, _grados);
}

StabBranching::StabBranching(Grafo& g, const VertexSet& subgrafo, ReservaClique * reserva) : FactoryDesigualdad(), _desigualdades(), _vertices(&subgrafo),
		_grados(g.grados<double>()),
		_param(RD, Goloso, RD, Clique, g.getN(), 3, 25, 0.15, 40), _clique(g.getN()),
		_nocliqueados(g.getN()), _reserva(reserva), _ninitialm(0), _grafo(g)
{
	_eleccionClqFactory = new GeneradorClique(_vertices, _grados);
}

StabBranching::~StabBranching()
{
	delete _grados;
	delete _eleccionClqFactory;
}

list<Desigualdad*>& StabBranching::branchNone() {
	_desigualdades.clear();
	edgeCliqueCover(*_vertices);

	return _desigualdades;
}

void StabBranching::cliqueCover(const VertexSet& subgrafo)
{
	if (_reserva != NULL && !_reserva->esActiva())
		return;

	GeneradorClique * eleccionClq = _eleccionClqFactory->newInstance(&_grafo, &_param);
	_nocliqueados.copyAll(subgrafo);

	while (!_nocliqueados.isEmpty())
	{
		_clique.removeAll();
		eleccionClq->cliqueSueltaMaximal(&_nocliqueados, &_clique);
//		_clique.print();

		if (_reserva == NULL)
		{
			Desigualdad* ret = newDesigualdad();
			Lista& lc = _clique.lista();
			for (int i = 0; i < lc.cantidad(); i++)
				ret->setCoeficiente(lc[i],1);
			ret->setRHS(1);
			ret->setAsRank();

			_desigualdades.push_back(ret);
		}
		else if (_clique.size() > 2 && _clique.weight() >= 0.85)
			_reserva->agregaClique(_clique);

		_nocliqueados.removeAll(_clique);
	}

	delete eleccionClq;
}

void StabBranching::edgeCliqueCover(const VertexSet& subgrafo)
{
	GeneradorClique * eleccionClq = _eleccionClqFactory->newInstance(&_grafo, &_param);
	Grafo nocliqueadas(_grafo.getN());
	nocliqueadas.copySubgrafo(_grafo, subgrafo);
	_nocliqueados.copyAll(subgrafo);

	while (!_nocliqueados.isEmpty())
	{
		_clique.removeAll();
		if (!eleccionClq->cliqueSueltaMaximal(&_nocliqueados, &_clique))
			break;
		_nocliqueados.removeAll(_clique);

		Desigualdad* ret = newDesigualdad();
		for (VertexSetIterator itu = _clique.begin(); itu != _clique.end(); ++itu) {
			ret->setCoeficiente(*itu,1);
			nocliqueadas.delVecinos(*itu, _clique);
		}
		ret->setRHS(1);
		ret->setAsRank();
		_ninitialm++;

		_desigualdades.push_back(ret);
	}

	VertexSet candidatos(_grafo.getN());
	VertexSet cobiertos(_grafo.getN());
	for (VertexSetIterator itu = nocliqueadas.vertices().begin(); itu != nocliqueadas.vertices().end(); ++itu)
	{
		cobiertos.add(*itu);
		while (nocliqueadas.vecinos(*itu).begin(*itu) != nocliqueadas.vecinos(*itu).end()) {
			_clique.removeAll();
			_clique.add(*itu);
			candidatos.copyAll(nocliqueadas.vecinos(*itu));
			candidatos.removeAll(cobiertos);
			eleccionClq->cliqueSuelta(&candidatos, &_clique);

			Desigualdad* ret = newDesigualdad();
			for (VertexSetIterator itu = _clique.begin(); itu != _clique.end(); ++itu) {
				ret->setCoeficiente(*itu,1);
				nocliqueadas.delVecinos(*itu, _clique);
			}
			ret->setRHS(1);
			ret->setAsRank();
			_ninitialm++;

			_desigualdades.push_back(ret);
		}
	}

	delete eleccionClq;
}

list<Desigualdad*>& StabStabBranching::branchZero(int v, VertexSet& fijos) {
	VertexSet Nv = _grafo.vecinos(v);

	_desigualdades.clear();
	Desigualdad* ret = newDesigualdad();
	for (VertexSetIterator it = Nv.begin(); it != Nv.end(); ++it)
		ret->setCoeficiente(*it,-1);
	ret->setRHS(-2);
	ret->setAsNotRank();
	_desigualdades.push_back(ret);

	if (fijos.size() <= 10)
	{
		_novecinos.copyAll(fijos);
		_novecinos.removeAll(Nv);
		for (VertexSetIterator u = _novecinos.begin(); u != _novecinos.end(); ++u)
		{
			_vecinosDeFijos.copyAll(Nv);
			_vecinosDeFijos.addAll(_grafo.vecinos(*u));
			ret = newDesigualdad();
			for (VertexSetIterator w = _vecinosDeFijos.begin(); w != _vecinosDeFijos.end(); ++w)
				ret->setCoeficiente(*w,-1);
			ret->setRHS(-3);
			ret->setAsNotRank();
			_desigualdades.push_back(ret);

			_vecinosDeFijos.add(v);
			_vecinosDeFijos.add(*u);
			cliqueCover(_vecinosDeFijos);
		}

		_novecinos.copyAll(fijos);
		_novecinos.removeAll(Nv);
		_vecinosDeFijos.copyAll(Nv);
		int z;
		int cant = 1;
		while ((z = _novecinos.least()) >= 0)
		{
			_novecinos.removeAll(_grafo.vecinos(z));
			_novecinos.remove(z);
			_vecinosDeFijos.addAll(_grafo.vecinos(z));
			cant++;
		}
		if (cant > 2)
		{
			ret = newDesigualdad();
			for (VertexSetIterator w = _vecinosDeFijos.begin(); w != _vecinosDeFijos.end(); ++w)
				ret->setCoeficiente(*w,-1);
			cant++;
			ret->setRHS(-cant);
			ret->setAsNotRank();
			_desigualdades.push_back(ret);
		}

		Nv.add(v);
		cliqueCover(Nv);
	}

	return _desigualdades;
}

list<Desigualdad*>& StabStabBranching::branchOne(int v) {
	_desigualdades.clear();

	VertexSet Nv = _grafo.vertices();
	Nv.removeAll(_grafo.vecinos(v));
	cliqueCover(Nv);

	return _desigualdades;
}
